#include <string.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <stdio.h>

#include "inner.h"

#define MAX_CACHE_SIZE   (1ULL<<20)        // 1MB for test 1048576 B
#define MAX_MAPPED_PG    (MAX_CACHE_SIZE/PAGE_SIZE) // 1048576/4096 = 256 个
#define EVECT_NUM        (128)

#define PAGE_HASH_NUM    (MAX_MAPPED_PG) // 256
#define PAGE_HASH_MASK   (MAX_MAPPED_PG - 1) //  255

#define PG_DIRTY    (1<<0) // 1
#define PG_BUSY     (1<<1) // 2

// 双向循环链表 中的节点
struct node_s {
    struct node_s *prev;
    struct node_s *next;
};

// 缓存系统中 free busy 链表中的节点
struct pg_s {
    uint32_t flags;        // off:0：PG_DIRTY or PG_BUSY 作用
    uint32_t reserv;       // off:4：
    gpid_t gpid;           // off:8： global page id
    struct page_s *buf;    // off:16：指向的是page, 应该被 mmap
    struct node_s hash;    // for hash, off:24：
    struct node_s link;    // for lru, off:40：
};

// 缓存器
struct cache_s {
    uint64_t mapped_num;// 映射的是 pg_s buf 字段
    uint64_t busy_num; //  使用的?
    uint64_t free_num; //  空闲的?
    struct node_s hash[PAGE_HASH_NUM]; // 256个 数组中存放的是 pg_s 中的 hash 字段
    // free 节点指向的是 head 节点，head 节点的 prev 指向 tail 节点，组成循环链表，这一点有点绕。
    struct node_s free;   // free list head，LRU 链表，使用完一个页面后，将页面放在最前面，从尾部开始淘汰
    struct node_s busy;   // busy list head，LRU 链表，get()时，将页面放在首部
};

// 链表 head 头初始化设置
void list_init(struct node_s *h) {
    h->prev = h;
    h->next = h;
}

// n 插入在 h 链表的最后尾部, 当 h 后面有节点 m 时, n 选择横插在 m 之后, 并不会插在 h 后面;
// h->m  +n  =>  h->m->n
// 其中 h.prev 指向 n ; n.next 指向 h ; 组成双向循环链表;
void list_add_tail(struct node_s *n, struct node_s *h) {
    struct node_s *prev = h->prev;
    struct node_s *next = h;

    n->prev = prev;
    n->next = next;
    prev->next = n;
    next->prev = n;
}

// n 插入在 h 的正后方，当 h 后面有节点 m 时, n 选择横插在 h 与 m 之间, 并不会插在 m 后面;
// h->m  +n  =>  h->n->m
// 其中 h.prev 指向 m ; m.next 指向 h ; 组成双向循环链表;
void list_add(struct node_s *n, struct node_s *h) {
    struct node_s *prev = h;
    struct node_s *next = h->next;

    n->prev = prev;
    n->next = next;
    prev->next = n;
    next->prev = n;
}

// 删除那个就传那个，因为这个有前节点跟后节点
void list_del(struct node_s *n) {
    struct node_s *prev = n->prev;
    struct node_s *next = n->next;

    prev->next = n->next;
    next->prev = n->prev;
    n->prev = n;
    n->next = n;
}

int list_empty(struct node_s *h) {
    return h->next == h;
}

// link 字段 得到 pg_s
struct pg_s *link_pg(struct node_s *n) {
    // 把 0 强转为 (struct pg_s *) 类型指针，再对这个 指针 取址, 然后再 获得 link 字段
    // 再把 link 字段 强转为 (char *), 然后再强转为 (long)类型
    long off = (long) (char *) (&((struct pg_s *) 0)->link);
    char *ptr = (char *) n - off;
    return (struct pg_s *) ptr;
}

// hash 字段 得到 pg_s
struct pg_s *hash_pg(struct node_s *n) {
    long off = (long) (char *) (&((struct pg_s *) 0)->hash);
    char *ptr = (char *) n - off;
    return (struct pg_s *) ptr;
}

// hash 表中节点的持久化，可能包括 free busy 节点
void dump_cache(kvdb_t d) {
    int i;
    struct cache_s *ch = d->ch;
    struct node_s *h, *n;
    struct pg_s *p;

    fprintf(stderr, "dump_cache(): \n");
    fprintf(stderr, "  mapped_num = %lu\n", ch->mapped_num);
    fprintf(stderr, "  busy_num = %lu\n", ch->busy_num);
    fprintf(stderr, "  free_num = %lu\n", ch->free_num);
    // 256
    for (i = 0; i < PAGE_HASH_NUM; i++) {
        h = &(ch->hash[i]);
        // 每一个 hash 节点 都是一个双向循环链表
        if (list_empty(h)) {
            // 下一个槽位
            continue;
        }
        // 遍历hash表槽位节点组成的链表
        for (n = h->next; n != h; n = n->next) {
            // 获得 hash 字段 的 pg_s 节点
            p = hash_pg(n);
            // 打印 pg_s 结构
            fprintf(stderr, "  i=%4d p=%p  flg=%8x  gpid=%8lu  buf=%p \n", i, p, p->flags, p->gpid, p->buf);
        }
    }
    fprintf(stderr, "\n");
}

// 打开数据库后, 开始执行缓存器初始化, 双向链表的初始化
void init_cache(kvdb_t db) {
    struct cache_s *ch;
    int i;
    // 堆分配内存
    ch = (struct cache_s *) malloc(sizeof(*ch));
    kvdb_assert(ch != NULL);

    db->ch = ch;
    ch->mapped_num = 0;
    // 初始化各个节点头
    list_init(&(ch->free));
    list_init(&(ch->busy));
    // hash 表默认 256 大小
    for (i = 0; i < PAGE_HASH_NUM; i++) {
        // 初始化 hash 表 256大小。每个头节点，都有后续的链表组成
        list_init(&(ch->hash[i]));
    }
}

// 传递节点头，并具体执行函数
void walk_link_page(struct node_s *head, void (*fn)(struct pg_s *)) {
    struct node_s *n;
    struct pg_s *p;
    // 从head头节点到尾部，并且不会从尾部遍历到头部
    for (n = head->next; n != head; n = n->next) {
        // 获得 link 字段的 pg_s 结构 , for lru
        p = link_pg(n);
        // 执行传递进来的函数
        fn(p);
    }
}

// 同步刷盘指定脏页 pg_s 结构
void sync_page(struct pg_s *p) {
    int ret;
    // 是否是脏页
    if ((p->flags & PG_DIRTY) == 0) {
        return;
    }
    // 是脏页
    // 把在该内存段的某个部分或者整段中的修改写回到被映射的文件中（或者从被映射文件里读出）
    ret = msync(p->buf, PAGE_SIZE, MS_SYNC);
    kvdb_assert(ret == 0);
    p->flags &= ~PG_DIRTY;
}

// 同步所有的页
void sync_all_page(kvdb_t db) {
    // free 节点链表进行刷盘
    walk_link_page(&db->ch->free, sync_page);
    // busy 节点链表进行刷盘
    walk_link_page(&db->ch->busy, sync_page);
}

// 销毁 page
void evict_page(kvdb_t db, struct pg_s *p) {
    int ret;
    // 如果是脏页
    if ((p->flags & PG_DIRTY) != 0) {
        ret = msync(p->buf, PAGE_SIZE, MS_SYNC);
        kvdb_assert(ret == 0);
        p->flags &= ~PG_DIRTY;
    }
    list_del(&(p->link));
    list_del(&(p->hash));
    // 结束映射，释放内存段
    ret = munmap(p->buf, PAGE_SIZE);
    kvdb_assert(ret == 0);
    db->ch->mapped_num--;
    if (p->flags & PG_BUSY) {
        db->ch->busy_num--;
    } else {
        db->ch->free_num--;
    }
    free(p);
}

void exit_cache(kvdb_t db) {
    struct pg_s *p;

    while (!list_empty(&(db->ch->free))) {
        // 获得 free 中的节点 node 的 pg_s 节点
        p = link_pg(db->ch->free.next);
        // 退出 mmap
        evict_page(db, p);
    }
    while (!list_empty(&(db->ch->busy))) {
        // 获得 busy 中的节点 node 的 pg_s 节点
        // todo p = link_pg(db->ch->free.next);
        p = link_pg(db->ch->busy.next);
        // 退出 mmap
        evict_page(db, p);
    }
    free(db->ch);
    db->ch = NULL;
}

// 计算全局唯一ID的 hash 槽，uint64_t 转 uint32_t
uint32_t pg_hash(gpid_t gpid) {
    uint32_t a, b, c;
    a = (uint32_t) gpid;
    b = (uint32_t) (gpid >> 22);
    c = (uint32_t) (gpid >> 44);
    // PAGE_HASH_MASK 255 大小
    return (uint32_t) ((a ^ b ^ c) & PAGE_HASH_MASK);
}

//1️⃣ 仅仅是从 hash 表中查找
struct pg_s *find_page(kvdb_t db, gpid_t gpid, uint32_t bucket) {
    struct node_s *head, *n;
    struct pg_s *p;
    // 这个hash表中bucket槽中的头节点
    head = &(db->ch->hash[bucket]);
    // 跳过头节点, 逐一进行排查
    for (n = head->next; n != head; n = n->next) {
        // 获得 hash 节点 node 的 pg_s 节点
        p = hash_pg(n);
        // 如果从hash表中找到了，也有可能找不到
        if (p->gpid == gpid) {
            return p;
        }
    }
    return NULL;
}

// 先从缓存中的 hash 表中查找，没有找到就重新分配映射，再放到缓存 hash 表中
pg_t get_page(kvdb_t db, gpid_t gpid) {
    uint32_t bucket; //
    struct pg_s *p; //
    // 内存中映射数量超过了 256 个
    if (db->ch->mapped_num >= MAX_MAPPED_PG) {
        // 判断 free 链表节点是否不为空 && 并且逐出 51% 左右
        while (!list_empty(&(db->ch->free)) && db->ch->mapped_num >= (MAX_MAPPED_PG / 2)) {
            // 对 free 链表 进行 缩减
            // 获得 link 字段的节点的 pg_s
            // 问：为啥用 pre 啊？？？莫非 free 节点默认的是 尾节点？？？
            // 答：不是，free默认的还是head节点，只是根据本项目编写的双向循环链表，free.prev 指向的是 tail 节点
            p = link_pg(db->ch->free.prev);
            // hash 表逐出，free 链表逐出
            evict_page(db, p);
        }
    }// if over
    // 根据全局唯一ID 找 hash 表的槽位
    bucket = pg_hash(gpid);
    // 在缓存中的 hash 表查找节点, 并不是 真正的 page 页, 而是 pg_s 数据
    p = find_page(db, gpid, bucket);
    // 有可能缓存在内存中, 也有可能不在内存中
    if (p != NULL) {// 说明在缓存器中的 hash 表中
        // 断言：当前页面 必须不是 busy ; 也不一定吧？
        kvdb_assert((p->flags & PG_BUSY) == 0);
        // 在 free or busy 列表中删除这个节点
        list_del(&(p->link));
        // 用 link 加入在 busy 中添加这个节点
        list_add(&(p->link), &(db->ch->busy));
        db->ch->free_num--;
    } else { // 没有在缓存中查到
        // page 页面所在数据文件的偏移地址 (4KB空间的首地址)
        uint64_t pos;
        // 分配空间
        p = malloc(sizeof(*p));
        kvdb_assert(p != NULL);
        p->flags = 0;
        p->gpid = gpid;
        // 从整个数据文件中计算 pos: 2MB + gp_id * 4KB, 挺方便的啊, 固定4KB大小的好处, 利用逻辑序号可获得具体地址数据
        pos = get_page_pos(gpid);
        // mmap 将数据库文件映射在内存中，4KB大小 应设在 buf 中
        p->buf = (struct page_s *) mmap(NULL, PAGE_SIZE,
                                        PROT_READ | PROT_WRITE,
                                        MAP_SHARED,
                                        db->fd, pos);
        kvdb_assert(p->buf != NULL);
        // 根据全局唯一ID 找 hash 槽 bucket，然后插入到这个列表中
        list_add(&(p->hash), &(db->ch->hash[bucket]));
        // 此时 page 页数据为空，放入 busy 中
        list_add(&(p->link), &(db->ch->busy));
        // buf 映射数量++
        db->ch->mapped_num++;
    }
    kvdb_assert((p->flags & PG_BUSY) == 0);
    p->flags |= PG_BUSY;
    db->ch->busy_num++;
    return p;
}

// 放入到 free 列表中，省的之后进行 malloc() 分配
void put_page(kvdb_t db, pg_t p) {
    kvdb_assert((p->flags & PG_BUSY) != 0);
    // link 节点所在的链表进行删除，busy 中剔除
    list_del(&(p->link));
    // link 节点加在 free 链表上
    list_add(&(p->link), &(db->ch->free));
    // 当前节点置为 空闲状态
    p->flags &= ~PG_BUSY;
    db->ch->free_num++;
    db->ch->busy_num--;
}

struct page_s *get_page_buf(kvdb_t db, pg_t pg) {
    return pg->buf;
}

void mark_page_dirty(kvdb_t db, pg_t pg) {
    pg->flags |= PG_DIRTY;
}


